package com.arron.algorithm.leetcodetop100.回溯.岛屿;

public class 统计封闭岛屿的数目 {



    public int closedIsland(int[][] grid) {

        //先将位于边缘的岛屿将其淹没，剩下的岛屿则全是封闭岛屿

        int m = grid.length;
        int n = grid[0].length;

        //淹没上边的岛屿
        for (int i = 0; i < n; i++) {
             if (grid[0][i] == 0){
                  dfs(grid,0,i);
             }
        }
        //淹没下边的岛屿
        for (int i = 0; i < n; i++) {
            if (grid[m-1][i] == 0){
                dfs(grid,m-1,i);
            }
        }
        //淹没左边的岛屿
        for (int i = 0; i < m; i++) {
            if (grid[i][0] == 0){
                dfs(grid,i,0);
            }
        }
        //淹没右边的岛屿
        for (int i = 0; i < m; i++) {
            if (grid[i][n-1] == 0){
                dfs(grid,i,n-1);
            }
        }
        int count = 0;
        for (int i = 1; i < m-1; i++) {
            for (int j = 1; j < n-1; j++) {
                if (grid[i][j] == 0){
                    dfs(grid,i,j);
                    count++;
                }

            }

        }
        return count;
    }

    private void dfs(int[][] grid, int i, int j) {

        if (i < 0 || j<0||i>=grid.length || j >= grid[0].length || grid[i][j] == 1){
            return;
        }



        grid[i][j] = 1;

        //下边
        dfs(grid,i+1,j);
        //上边
        dfs(grid,i-1,j);
        //左边
        dfs(grid,i,j-1);
        //右边
        dfs(grid,i,j+1);

    }

}
